# 代码编写者： 李朔
# 开发时间： 2021/9/12 11:21

def Heapify(nums,i,nums_len):
    '''
    调整堆：一次
    :param nums:
    :param i:
    :param nums_len:
    :return:
    '''
    #左右孩子结点索引，当前需调整的结点的索引
    l,r,max=2*i+1,2*i+2,i
    #当前的父节点比其孩子结点value小，就进行调整
    if l<nums_len and nums[max]<=nums[l]:
        max=l
    if r<nums_len and nums[max]<=nums[r]:
        max=r
    if max!=i:
        nums[max],nums[i]=nums[i],nums[max]
        #同时我们需要堆它下面的交换了值的子节点进行调整
        Heapify(nums,max,nums_len)
    else:
        return None
def bigMaxHeapCreation(nums,nums_len):
    '''
    大根堆的创建工作
    :param nums: 待排序序列
    :param nums_len: 序列长度
    :return:
    '''
    #从最后一个非叶子结点开始调整根堆，直到根节点为止
    for i in range(int(len(nums)/2)-1,-1,-1):
        Heapify(nums,i,nums_len)

nums=[19,30,21,10,40,75,88]
bigMaxHeapCreation(nums,len(nums))
print("大根堆调整结果：")
print(nums)
#开始进行结果的输出，也就是每一轮输出一个最大值，同时进行根堆的调整工作
nums_len=len(nums)
for i in range(len(nums)-1,0,-1):
    #将根节点值和最后一个叶子节点交换位置
    nums[i],nums[0]=nums[0],nums[i]
    nums_len-=1
    Heapify(nums,0,nums_len)
print(nums)